package 阿里机试;

import java.util.Arrays;

/**
 * Created by hest0 on 2017/8/2.
 */
public class KMP算法最精简版 {
    public static void main(String[] args) {
        String s = "ABCaaab";
        String m = "aaab";
        System.out.println(getIndexOf(s, m));
    }

    private static int getIndexOf(String s, String m) {
        if (s == null || m == null || s.length() < m.length())
            return -1;

        char[] sa = s.toCharArray();
        char[] ma = m.toCharArray();
        int i = 0, j = 0;

        int[] next = getNextArray(m);
        System.out.println(Arrays.toString(next));

        while (i < sa.length && j < ma.length) {
            if (sa[i] == ma[j]) {
                i++;
                j++;
            } else if (next[j] == -1)
                i++;
            else
                j = next[j];
        }

        return j == m.length() ? i - j : -1;
    }

    private static int[] getNextArray(String m) {
        if (m.length() == 1)
            return new int[]{1};

        char[] ma = m.toCharArray();
        int[] next = new int[m.length()];
        next[0] = -1;
        next[1] = 0;
        int cn = 0, pos = 1;

        while (pos < next.length - 1) {
            if (ma[cn] == ma[pos])
                next[++pos] = ++cn;
            else if (cn > 0)
                cn = next[cn];
            else
                next[++pos] = 0;
        }

        return next;
    }
}
